package com.hanxiaozhang.no10leetcode.array;

/**
 * 〈一句话功能简述〉<br>
 * 〈〉
 * 给一个二维数组和一个单词，判断该单词是否在数组中 单词由数组中相邻的元素组成，
 * 相邻可以理解为上下左右的所有相邻元素，同一个字母只能使用一次。
 * 实例:
 * board = [
 * ['A','B','C','E'],
 * ['S','F','C','S'],
 * ['A','D','E','E']
 * ]
 * 给定单词 "ABCCED", 返回 true
 * 给定单词 "SEE", 返回 true
 * 给定单词 "ABCB", 返回 false
 * <p>
 * 这道题自己摸搜出来的，牛逼
 *
 * @author hanxinghua
 * @create 2024/1/23
 * @since 1.0.0
 */
public class No79WordSearch {

    public static void main(String[] args) {

        char[][] board = {
                {'A', 'B', 'C', 'E'},
                {'S', 'F', 'C', 'S'},
                {'A', 'D', 'E', 'E'}};

        String target1 = "ABCCED";
        String target2 = "SEE";
        String target3 = "ABCB";

        System.out.println(method1(board, target1));

    }


    /**
     * 方法1
     *
     * @param board
     * @param target
     * @return
     */
    private static boolean method1(char[][] board, String target) {
        char[] targets = target.toCharArray();

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                boolean judge = judge(board, i, j, targets, 0);
                if (judge) {
                    return true;
                }
            }
        }

        return false;
    }


    /**
     * 出一个位置开始，判断是否存在目标元素
     *
     * @param board
     * @param i           行
     * @param j           列
     * @param targets
     * @param targetIndex
     * @return
     */
    private static boolean judge(char[][] board, int i, int j, char[] targets, int targetIndex) {

        // 越界，返回false
        if (i < 0 || i >= board.length) {
            return false;
        }
        // 越界，返回false
        if (j < 0 || j >= board[0].length) {
            return false;
        }
        // 越界，返回false
        if (targetIndex >= targets.length) {
            return false;
        }

        // 当前位置元素配置
        if (board[i][j] == targets[targetIndex]) {
            // 处理到最后一个元素
            if (targetIndex == targets.length - 1) {
                return true;
            }
            char temp = board[i][j];
            board[i][j] = ' ';
            boolean flag = false;
            // 向上
            boolean judge1 = judge(board, i - 1, j, targets, targetIndex + 1);
            if (judge1) {
                flag = true;
            }
            // 向下
            boolean judge2 = judge(board, i + 1, j, targets, targetIndex + 1);
            if (judge2) {
                flag = true;
            }
            // 向左
            boolean judge3 = judge(board, i, j + 1, targets, targetIndex + 1);
            if (judge3) {
                flag = true;
            }
            // 向右
            boolean judge4 = judge(board, i, j - 1, targets, targetIndex + 1);
            if (judge4) {
                flag = true;
            }
            // 恢复现场
            board[i][j] = temp;
            return flag;
        }

        return false;

    }


    /**
     * 出一个位置开始，判断是否存在目标元素（优化版）
     *
     * @param board
     * @param i           行
     * @param j           列
     * @param targets
     * @param targetIndex
     * @return
     */
    private static boolean judge_optimize(char[][] board, int i, int j, char[] targets, int targetIndex) {

        // 边界条件：越界，返回false
        if (i < 0 || i >= board.length) {
            return false;
        }
        // 边界条件：越界，返回false
        if (j < 0 || j >= board[0].length) {
            return false;
        }
        // 边界条件：越界，返回false
        if (targetIndex >= targets.length) {
            return false;
        }
        // 当前位置元素不配置
        if (board[i][j] != targets[targetIndex]) {
            return false;
        }
        // 当前位置元素配置时，处理到最后一个元素，证明处理成功
        if (targetIndex == targets.length - 1) {
            return true;
        }
        // 临时变量
        char temp = board[i][j];
        board[i][j] = ' ';
        //             向上
        boolean flag = judge_optimize(board, i - 1, j, targets, targetIndex + 1) ||
                // 向下
                judge_optimize(board, i + 1, j, targets, targetIndex + 1) ||
                // 向左
                judge_optimize(board, i, j + 1, targets, targetIndex + 1) ||
                // 向右
                judge_optimize(board, i, j - 1, targets, targetIndex + 1);
        // 恢复现场 ，作用保证数据不重复使用
        board[i][j] = temp;
        return flag;
    }


}
